Parallel data connections between processors within a computer system can be accomplished in various ways. One such way is called a hypercube, and can have various dimensions. An n-cube network of processors or nodes, called an n-dimensional hypercube, consists of 2" identical nodes that are interconnected to each other so that each node has n neighbors. The nodes are given a binary number address and they are connected in such a manner that the binary number addresses between connected nodes differs in one and only one bit. FIG. 1 shows an example of a prior art hypercube where n =3. As shown in FIG. 1, when n=3, an n-cube can be represented as an ordinary cube in three dimensions where the vertices are the 8 (2.sup.3) nodes of the 3-cube and the edges represent data communication paths between the nodes.
Hypercubes have shown to be superior over simpler interconnects because of faster communication between the nodes. In a Hypercube data transfers are performed by passing messages between nearest neighbors. Thus a data packet which must travel between a starting node and a destination node may cross a sequence of nodes between the starting and destination nodes.
A key disadvantage of the hypercube topology is the growth rate of the data communication path count between neighbors as n increases. As n increases, each node becomes more difficult to design and fabricate due to this increasing number of connections. This growth rate, coupled with pin limitations on VLSI chips, continues to seriously limit the scalability of the hypercube topology to massively parallel systems. Additionally, the inherent bi-directional nature of the data communication paths within the hypercube prevents it from being readily used with naturally unidirectional media, such as fiber-optic media. Most of the existing hypercube connected multi-processor systems use two physical data communication paths, one for transmitting data in each direction, to allow parallel transmission between two adjacent nodes of the hypercube.
There is a need in the art then for a method of defining a hypercube using single unidirectional data communication paths. There is a further need for a method of determining the data communication paths that must be traversed when sending a message from one node of the hypercube to a second node. The present invention meets these needs.